import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-6 20:28
 * @description：B树的节点
 * @modified By：
 * @version:
 */
public class BTreeNode<K,V> {

    //默认是5阶树
    private Integer DEFAULT_T = 5;
    //根节点
    private Node<K, V> root;

    private int m = DEFAULT_T;
    //非根节点的最小项数，体现的是除了根节点，其余节点都是分裂而来的！

    //这里体现了除根节点和叶子节点外每个节点的最小儿子数量
    private int nodeMinSize = m/2;

    //节点的最大儿子数
    private int nodeMaxSize = m;
    //节点的最大关键字数
    private int keyMaxSize = m-1;
    //节点的最小关键字数
    private int keyMinSize = m/2;
    //比较函数对象
    private Comparator<K> kComparator;
    //查找

    public BTreeNode(Integer DEFAULT_T) {
        this.root = new Node<>();
        this.root.setLeaf(true);
        m = DEFAULT_T;
        nodeMinSize = m/2;
        nodeMaxSize = m;
        keyMaxSize = m-1;
        keyMinSize = m/2;
        this.DEFAULT_T = DEFAULT_T;
    }

    public int getKeyMaxSize() {
        return keyMaxSize;
    }

    public int getKeyMinSize() {
        return keyMinSize;
    }

    public void setDEFAULT_T(Integer DEFAULT_T) {
        this.DEFAULT_T = DEFAULT_T;
    }

    public void setRoot(Node<K, V> root) {
        this.root = root;
    }

    public void setM(int m) {
        this.m = m;
    }

    public void setNodeMinSize(int nodeMinSize) {
        this.nodeMinSize = nodeMinSize;
    }

    public void setNodeMaxSize(int nodeMaxSize) {
        this.nodeMaxSize = nodeMaxSize;
    }

    public void setkComparator(Comparator<K> kComparator) {
        this.kComparator = kComparator;
    }

    public Integer getDEFAULT_T() {
        return DEFAULT_T;
    }

    public Node<K, V> getRoot() {
        return root;
    }

    public int getM() {
        return m;
    }

    public int getNodeMinSize() {
        return nodeMinSize;
    }

    public int getNodeMaxSize() {
        return nodeMaxSize;
    }

    public Comparator<K> getkComparator() {
        return kComparator;
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 14:12
     * @Description 内部类，封装搜索结果
     */
    class SearchResult<V> {
        private boolean isExist;
        private V value;
        private int index; //索引

        //构造方法，将查询结果封装入对象
        public SearchResult(boolean isExist, int index, V value) {
            this.isExist = isExist;
            this.index = index;
            this.value = value;
        }

        public boolean isExist() {
            return isExist;
        }

        public V getValue() {
            return value;
        }

        public int getIndex() {
            return index;
        }
    }
    /**
     * create by: 冯涛滔
     * description: 私有内部类 代表关键字以及数据域
     * create time: 2020-5-6 21:28
     *
     * @params
     * @return
     */
    class Entry<K, V> {

        private K key;
        private V value;

        public void setKey(K key) {
            this.key = key;
        }

        public K getKey() {
            return this.key;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public V getValue() {
            return this.value;
        }
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public Entry() {
        }
        @Override
        public String toString() {
            return "key: " + this.key + " , ";
        }

    }
    /**
     * create by: 冯涛滔
     * description: 节点列表
     * create time: 2020-5-9 20:28
     * @params entries关键字列表  children儿子节点列表 索引为2的关键字的左子树为2右子树为2+1
     * @return
     */
    class Node<K,V> {

        //关键字列表
        private List<Entry<K,V>> entries;
        //子树列表
        private List<Node<K, V>> children;
        //是否为叶子节点
        private boolean leaf;
        //键值比较函数对象，如果采用倒序或者其它排序方式，传入该对象
        private Comparator<K> kComparator;
        //比较两个key，如果没有传入自定义排序方式则采用默认的升序
        /**
         * create by: 冯涛滔
         * description: 默认情况下是返回key2.comPareto(key1)也就是key2>key1 返回大于0的值 == 等于0 <小于0
         * create time: 2020-5-9 20:30
         * @params [key1, key2]
         * @return int
         */
        public int compare(K key1, K key2) {

            return this.kComparator == null ? ((Comparable<K>) key2).compareTo(key1) : kComparator.compare(key1, key2);
        }
        Node() {
            this.entries = new LinkedList<Entry<K, V>>();
            this.children = new LinkedList<Node<K, V>>();
            this.leaf = false;
        }
        Node(Comparator<K> kComparator) {
            this();
            this.kComparator = kComparator;
        }
        //返回本节点的关键字字数
        public int nodeSize() {
            return this.entries.size();
        }

        public List<Entry<K, V>> getEntries() {
            return entries;
        }

        public void setEntries(List<Entry<K, V>> entries) {
            this.entries = entries;
        }

        public List<Node<K, V>> getChildren() {
            return children;
        }

        public void setChildren(List<Node<K, V>> children) {
            this.children = children;
        }

        public boolean isLeaf() {
            return leaf;
        }

        public void setLeaf(boolean leaf) {
            this.leaf = leaf;
        }

        public Comparator<K> getkComparator() {
            return kComparator;
        }

        public void setkComparator(Comparator<K> kComparator) {
            this.kComparator = kComparator;
        }

        /**
         * create by: 冯涛滔
         * description: 查找当前节点有没有这个key本质上就是一个二分搜索 index是给插入关键字用的判断是要插入到mid的哪个位置
         * 关于返回值的index要明白 索引为0的关键字的左子树为0 右子树为0+1 经过推断可以一直延续下去
         * 所以如果没找到key就会返回合适的子树索引
         * 索引可以直接使用 如果是叶子节点
         * create time: 2020-5-7 20:29
         * @params [key]
         * @return BTreeNode<K, V>.SearchResult<V>
         */
        public SearchResult<V> search(K key){
            int left = 0; //左指针
            int right = this.nodeSize()-1;//右指针
            V res = null;//返回值
            int mid = (left+right)/2;//中间的位置
            boolean isExist = false; //判断是否找到了
            int index = 0; //要找的关键字的下标
            while(left<right){
                mid = (left+right)/2;//中间的位置
                Entry<K,V> midEntry = this.entries.get(mid);//拿到中间的关键字
                int comparator = this.compare(key,midEntry.getKey());
                if(comparator == 0){//找到了
                    break;
                }else {
                    if(comparator==1){//midKey大于key 在左侧
                        right = mid-1;
                    }else{//在右侧
                        left = mid+1;
                    }
                }
            }
            //二分查找结束了
            if(left<right){ //证明查找是被提前结束的 所以就是找到了
                isExist = true;
                index = mid;
                res = this.entries.get(mid).getValue();
            }else{
                if(left == right){
                    K midKey = this.entries.get(left).getKey();//虽然没有找到key但是找到了离key最近的一个关键字
                    int comRe = compare(midKey, key); //判断key和关键字哪个大
                    if(comRe == 0){//找到了
                        isExist = true;
                        index = mid;
                        res = this.entries.get(mid).getValue();
                    }else{
                        if(comRe>0){ //key大 那么就是关键字的右子树
                            isExist = false;
                            index = left + 1;
                            res = null;
                        }else { //key小 返回当前left的左子树
                            isExist = false;
                            index = left ;
                            res = null;
                        }
                    }
                }else {//走到这里也是因为right<left 意思就是 要查找的key比left要小所以返回left关键字的左子树
                    isExist = false;
                    index = left;
                    res = null;
                }
            }
            return new SearchResult<V>(isExist, index, res);
        }

        //删除给定索引位置的项
        public Entry<K, V> removeEntry(int index) {
            Entry<K, V> re = this.entries.get(index);
            this.entries.remove(index);
            return re;
        }

        //得到index处的项
        public Entry<K, V> entryAt(int index) {
            return this.entries.get(index);
        }
        //将新项插入指定位置 这里设置成private封装
        // 会使用到这里只有两种情况一个是叶子节点的插入关键字以及确定好了位置
        //节点分裂但是也已经确定好了位置
        private void insertEntry(Entry<K, V> entry, int index) {
            this.entries.add(index, entry);
        }
        //将新关键字插入 如果存在相同的关键字key不允许插入
        public boolean insertEntry(Entry<K,V> entry){
            SearchResult<V> result = search(entry.getKey()); //这里会返回适合的节点
            if (result.isExist()) { //如果有了相同的key就不然插入
                return false;
            } else {
                insertEntry(entry, result.getIndex());
                return true;
            }
        }
        //更新项，如果项存在，更新其值并返回原值，否则直接插入
        public V putEntry(Entry<K, V> entry) {
            SearchResult<V> re = search(entry.getKey());
            if (re.isExist) {
                Entry oldEntry = this.entries.get(re.getIndex());
                V oldValue = (V) oldEntry.getValue();
                oldEntry.setValue(entry.getValue());
                return oldValue;
            } else {
                insertEntry(entry);
                return null;
            }
        }
        //获得指定索引的子节点
        public Node childAt(int index) {
            return this.children.get(index);
        }

        //删除给定索引的子节点
        public void removeChild(int index) {
            this.children.remove(index);
        }

        //将新的子节点插入到指定位置
        public void insertChild(Node<K, V> child, int index) {
            this.children.add(index, child);
        }
    }
    private V search(Node<K, V> root, K key) {
        SearchResult<V> re = root.search(key); //查找根节点
        if (re.isExist) {
            return re.value;
        } else {
            //回归条件
            if (root.leaf) {//找到了叶子节点也没找到就不需要继续寻找下去了
                return null;
            }
            int index = re.index;
            //递归搜索子节点
            return (V) search(root.childAt(index), key);
        }
    }
    public V search (K key){
        return search(this.root, key);
    }
    /**
     * create by: 冯涛滔
     * description:
     * 1. 判断是不是叶子节点
     * 2. 是就插入 不是就是找到适合插入的子树递归插入
     * 3.插入完成之后检查树的性质有没有被破坏 如果有就进行节点分裂
     * create time: 2020-5-11 21:31
     * @params [root, entry, father, number] root进行插入的节点 entry要插入的关键字 father root的父节点 number root在父节点的下标
     * @return boolean
     */
    public boolean insertNotFull2(Node<K,V> root,Entry<K,V> entry,Node<K,V> father,int number){

        if(root.isLeaf()){ //因为插入都是在叶子节点发生的
            root.insertEntry(entry); //这里进行插入 可能会超过当前节点的关键字容量 我们后面会处理
        }else{
            //如果没有到叶子节点就要找到适合的下一层
            SearchResult<V> re = root.search(entry.key); //这里会返回适合的下一层的索引
            if(re.isExist){ //找到了相同的索引 所以不能添加 //这里就不写覆盖了
                return false;
            }
            int index = re.index; //下一层的索引
            Node<K,V> searchChild = root.childAt(index);
            insertNotFull2(searchChild,entry,root,index);
        }
        //到了这里就是插入完了就要检查关键字是否超过了容量
        if(root.entries.size()>getKeyMaxSize()||root.children.size()>getNodeMaxSize()){ //判断关键字和儿子是否超过容量
          splitNode2(father,root, number);
        }
        return true;
    }
    /**
     * create by: 睚雪
     * description: 
     * 1. 将节点以中间进行分割 midKey插入到父节点
     * 2. 创建一个新的节点将midKey左半边的关键字和孩子节点全部移植到新节点
     * 3. 将新节点插入到父节点的孩子列表 下标就是midKey的插入的位置
     * 4. 旧节点继承了以前的右半边的数据 位置也不需要动
     * 5. 如果是根节点分裂就树增加一层 midKey作为新的树根
     * create time: 2020-5-11 21:22
     * @params [fatherNode, splitNode, index] fatherNode要分裂的关键字的父节点 splitNode分裂的关键字 index分裂节点在父节点的索引下标
     * index的意义其实是分裂节点的mid关键字要插入的位置索引 同时也是分裂出来的左节点要插入的位置索引
     * @return void
     */
    private void splitNode2(Node<K, V> fatherNode, Node<K, V> splitNode,int index) {
        
        //关键字分裂
        Node<K,V> newNode = new Node<>(splitNode.kComparator);//新的节点 左半边
        newNode.setLeaf(splitNode.isLeaf()); //分裂的节点是叶子的话新节点也是叶子
        Entry<K, V> midEntry = splitNode.entries.get(m / 2);//拿到中间的关键字

        for (int i = 0; i <m/2; i++) { //拿到左半部分的关键字一边拿一边删 还有儿子节点要处理
            newNode.entries.add(splitNode.entries.get(0));
            splitNode.entries.remove(0);//删除
        }
        //如果分裂的节点不是叶子节点，子节点一并跟随分裂
        if (!splitNode.isLeaf()) {
            for (int i = 0; i <= this.m/2 ; i++) {
                newNode.children.add(splitNode.children.get(0));
                splitNode.children.remove(0);

            }

        }
        splitNode.entries.remove(midEntry);
        if(fatherNode == null){//根节点分裂
            fatherNode = new Node<K, V>();
            fatherNode.setLeaf(false);
            fatherNode.insertChild(splitNode, 0);//插入根节点的右儿子 也就是原根节点
            this.root = fatherNode; //设置好新的根节点
        }

        fatherNode.insertEntry(midEntry);
        fatherNode.insertChild(newNode, index);
    }
    //插入一个新节点
    public boolean insertNode(Entry<K, V> entry) {
        //根节点满了，先分裂根节点
        if (root.nodeSize() > getKeyMaxSize()||root.nodeSize() >getNodeMaxSize()) {
            Node<K, V> newRoot = new Node<K, V>();
            newRoot.setLeaf(false);
            newRoot.insertChild(root, 0);
            splitNode2(newRoot, root, 0);
            this.root = newRoot;
        }
        return insertNotFull2(root, entry,null,0);
    }
    /**
     * @Author Nxy
     * @Date 2020/2/25 14:18
     * @Description 借助队列打印B树
     */
    public void output() {
        Queue<Node<K, V>> queue = new LinkedList<Node<K, V>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            for (int i = 0; i < node.nodeSize(); ++i) {
                System.out.print(node.entryAt(i) + " ");
            }
            System.out.println();
            if (!node.isLeaf()) {
                for (int i = 0; i <= node.children.size() - 1; ++i) {
                    queue.offer(node.childAt(i));
                }
            }
        }
    }
    public static void main(String[] args) {
        Random random = new Random();
        BTreeNode<Integer, Integer> btree = new BTreeNode<Integer, Integer>(3);
        List<Integer> save = new ArrayList<Integer>(30);
//        save.add(8290);
//        save.add(7887);
//        save.add(9460);
//        save.add(9928);
//        save.add(6127);
//        save.add(5891);
//        save.add(1592);
//        save.add(14);
//        save.add(8681);
//        save.add(4843);
//        save.add(1051);

        for (int i = 0; i < 20; ++i) {
            int r = random.nextInt(10000);
            save.add(r);
            System.out.print(r + "  ");
            BTreeNode.Entry en = btree.new Entry<Integer, Integer>();
            en.setKey(r);
            en.setValue(r);
//            BTree.Entry en = btree.new Entry<Integer, Integer>();
//            en.setKey(save.get(i));
            btree.insertNode(en);
        }

        System.out.println("----------------------");
        btree.output();
        System.out.println("----------------------");
//        btree.delete(save.get(0));
        btree.output();
    }

}


